package com.tgy.leetcode;

import java.util.LinkedList;

/**
 * @Author: tgy
 * @Date: 1/6/21 6:49 PM
 *
 *  https://leetcode-cn.com/problems/3sum-closest/
 */
public class _16_最接近的三数之和 {

    private int result = Integer.MAX_VALUE/2;

    public int threeSumClosest(int[] nums, int target) {

        find(nums,0,0,0,target);
        return result;
    }

    // n^3
    private void find(int[] nums, int index, int sum, int count, int target) {

        if (count >= 3) {

            if (Math.abs(sum - target) < Math.abs(result - target)) {

                result = sum;
            }
            return;
        }

        if (index >= nums.length) {
            return;
        }

        for (int i = index; i < nums.length; i++) {
            find(nums,i+1,sum + nums[i],count+1,target);
        }
    }

}
